leetcode 39. 组合总和(python)

您所在的位置:网站首页 组合总数 两个目标值 leetcode 39. 组合总和(python)

leetcode 39. 组合总和(python)

2024-06-21 04:51| 来源: 网络整理| 查看: 265

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。解集不能包含重复的组合。 示例 1:

输入: candidates = [2,3,6,7], target = 7,所求解集为:[ [7], [2,2,3]]示例 2:

输入: candidates = [2,3,5], target = 8,所求解集为:[  [2,2,2,2],  [2,3,3],  [3,5]]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: self.res = [] if len(candidates) target: # 剪枝操作,当当前数值大于目标值,则后续无需遍历 return if num < last: # 剪枝操作:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2] continue self.dfs(candidates,sublist+[num],target-num,num)

参考: https://blog.csdn.net/weixin_40546602/article/details/88357837 

递归函数 dfs(candidates,sublist,target,last),其中sublist记录当前满足条件的子数组,last为当前子数组的最后一个元素。

剪枝操作1:目标值小于元素数组的最小元素,则无需继续遍历

剪枝操作2:当前元素大于目标值,则后续元素一定大于目标值(数组已排序),不会满足条件,无需继续遍历

剪枝操作3:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2]



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3